package com.ayuer.chapter10;

import java.util.Arrays;

/**
 * 并查集
 */
public class DisJointSet {

    /**
     * 索引对应顶点
     * 元素对应有关系的顶点
     */
    int[] s;

    public DisJointSet(int size) {
        s = new int[size];
        for (int i = 0; i < size; i++) {
            s[i] = i;
        }
    }

    public int find(int v) { // v=2
        if (s[v] == v) {
            return v;
        }
        return s[v] = find(s[v]);// 路径压缩
    }

    public void union(int x, int y) {
        s[x] = y;
    }

    @Override
    public String toString() {
        return "DisJointSet{" +
                "s=" + Arrays.toString(s) +
                '}';
    }

    public static void main(String[] args) {
        DisJointSet disJointSet = new DisJointSet(7);
        System.out.println(disJointSet);
        disJointSet.union(1, 2);
        System.out.println(disJointSet);

    }
}
